# include <iostream>
#include <time.h>
using namespace std;


void merge(int A[],int L1,int R1,int L2,int R2){
    int i = L1,j = L2;
    int temp[100],index = 0;
    while(i<=R1&&j<=R2){
        if(A[i]<=A[j]){
            temp[index++] = A[i++];
        }else{
            temp[index++] = A[j++];
        }
    }
    while(i<=R1) {temp[index++] = A [i++];}
    while(j<=R1) {temp[index++] = A [j++];}
    for( i = 0;i<index;++i){
        A[L1+i] = temp[i];
    }
    return ;
}

void mergeSort(int A[],int left,int right){
    if(left<right){
        int mid = (left + right) >> 1;
        mergeSort(A,left,mid);
        mergeSort(A,mid+1,right);
        merge(A,left,mid,mid+1,right);
    }
    return;
}
int main(){

    int a[] = {5,4,3,1,5,56,648,9,31};
    mergeSort(a,0,8);
    for(auto c:a){
        cout<<c<<" ";
    }
    return 0;
}